﻿//优美的排列(medium) ：https://leetcode.cn/problems/beautiful-arrangement/submissions/609792502/
class Solution {
public:
    //vector<int> path;
    int ret;   //总数
    int check[16];  
    int countArrangement(int n) {
       // _n=n;
        // int arr[15]={0};   //1 2 3
        // for(int i=0;i<n;i++)
        // {
        //     arr[i]=i+1;
        // }
        //path.push_back(0);  //确保下标
        dfs(1,n);

        return ret;

    }
    void dfs(int pos,int n)
    {
        if(pos==n+1)
        {
            ret++;
            return;
        }
        for(int i=1;i<=n;i++)
        {
            if(check[i]==0 && (i%pos==0||pos%i==0))
            {
               // path.push_back(i);  
               check[i]=1;
                dfs(pos+1,n);

                //path.pop_back(); 
                 check[i]=0;
            }
        }
    }
};